package org.example.myleet.p1036;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

public class Solution {

    private static final int[][] DIRECTIONS = new int[][]{{0, -1}, {1, 0}, {0, 1}, {-1, 0}};

    //题目给出的迷宫边界范围
    private static final int MAX_WIDTH = 999999;
    private static final int MAX_HEIGHT = 999999;

    //根据题目数据范围，200个block最多可以围出来的空间是20000以内（最优的围蔽方式是从y轴[0,199]斜着直线到x轴[199,0]），因此BFS的遍历上限确定
    private static final int MAX_BESIEGED_BLOCK_NUM = 20000;

    public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
        if (blocked.length < 2) {
            return true;
        }
        //处理block加速查询
        HashMap<Long, int[]> blockMap = new HashMap<>(MAX_BESIEGED_BLOCK_NUM);
        for (int[] block : blocked) {
            blockMap.put(getPositionHash(block[0], block[1]), block);
        }
        //source和target都分别用BFS验证是否被block围蔽
        return bfsForTarget(source, target, blockMap) && bfsForTarget(target, source, blockMap);
    }

    /**
     * 用BFS验证source是否被block围蔽
     */
    private boolean bfsForTarget(int[] source, int[] target, HashMap<Long, int[]> blockMap) {
        HashSet<Long> visited = new HashSet<>(MAX_BESIEGED_BLOCK_NUM);
        Queue<int[]> queue = new LinkedList<>();
        long positionHash = getPositionHash(source[0], source[1]);
        queue.offer(source);
        visited.add(positionHash);
        while (!queue.isEmpty()) {
            if (visited.size() > MAX_BESIEGED_BLOCK_NUM) {
                //遍历了超过上限的位置，说明没有围蔽成功，source存在路径到达target
                return true;
            }
            int len = queue.size();
            for (int i = 0; i < len; ++i) {
                int[] position = queue.poll();
                if (null == position) continue;
                for (int j = 0; j < 4; ++j) {
                    //基于这一点向外扩展
                    int newX = position[0] + DIRECTIONS[j][0];
                    int newY = position[1] + DIRECTIONS[j][1];
                    if (newX < 0 || newX > MAX_WIDTH || newY < 0 || newY > MAX_HEIGHT || isBlocked(blockMap, newX, newY)) {
                        //越界的、被block的忽略
                        continue;
                    }
                    if (newX == target[0] && newY == target[1]) {
                        return true;
                    }
                    positionHash = getPositionHash(newX, newY);
                    if (visited.contains(positionHash)) {
                        //已经访问过的忽略
                        continue;
                    }
                    //加入队列进入下一会合搜索
                    queue.offer(new int[]{newX, newY});
                    visited.add(positionHash);
                }
            }
        }
        return false;
    }

    private long getPositionHash(int x, int y) {
        return (long) x * 1000000L + y;
    }

    private boolean isBlocked (HashMap<Long, int[]> blockMap, int x, int y) {
        return blockMap.containsKey(getPositionHash(x, y));
    }
}
